// 封装节点
export class Node {
    constructor(element) {
        this.element = element; // 1.要保存的元素;
        this.next = null; // 2.指向下一个节点;
    }
}

// 封装链表
export class LinkedList {
    // 链表头部和链表长度
    constructor() {
        this.head = null;
        this.length = 0;
    }
    //  append(element)：向列表尾部添加一个新的项
    append(element) {
        // 1.根据element创建Node对象
        const newNode = new Node(element);
        // 2.追加节点
        if (!this.head) {
            // 当head为null就说明链表中没有数据，然后追加一个节点在最后面
            this.head = newNode; // 直接将节点赋值给head就插入节点了
        } else {
            // 否则链表中有节点，
            let current = this.head;
            // 需要一个一个遍历到最后，将下一个节点放到当前节点的next，直到next为null（用到循环）
            while (current.next) {
                current = current.next
            }
            // 添加新节点
            current.next = newNode;
        }
        this.length++; // 追加了几个元素length就为几,说明链表有几个元素
    }
    //  inset(position,element)：向列表的特定位置插入一个新的项
    inset(postion, element) {
        // 1.越界问题
        if (postion < 0 || postion > this.length) return false; // 插入失败
        // 2.创建元素
        const newNode = new Node(element);
        // 3.插入元素
        if (postion === 0) {
            //  1· 在第一个插入
            newNode.next = this.head;
            this.head = newNode;
        } else {
            //  2· 在其他位置插入
            // 记录第一个节点
            let index = 0;
            let current = this.head; // 当前插入下标的元素
            let previous = null; // 前一个
            // 从第一个开始找,找到给定下标,然后插入元素
            while (index++ < postion) {
                // 循环一次,将当前插入的下标元素赋给前一个
                previous = current;
                // 并且当前插入的下标元素为下一个元素
                current = current.next;
            }
            // 前一个元素的下一个为插入元素
            previous.next = newNode;
            // 插入元素的下一个为当前查找的下标元素
            newNode.next = current;
        }
        this.length++
    }
    //  get(position)：获取对应的位置
    get(position) {
        // 1.越界问题
        if (position < 0 || position > this.length - 1) return null;
        // 查找该位置元素
        let index = 0;
        // 记录一下，先是第一个
        let current = this.head
        // 使用循环依次往后找
        while (index++ < position) {
            current = current.next
        }
        // 最后返回给定位置的元素
        return current.element
    }
    //  indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
    indexOf(element) {
        // 1.先获取第一个元素
        let index = 0;
        let current = this.head;
        // 2.开始查找
        while (current) {
            // 找到就返回
            if (current.element == element) {
                return index
            }
            // 没找到就继续找下一个
            current = current.next
            index++
        }
        // 最后也没找到就返回-1
        return -1
    }
    //  removeAt(position)：从列表的特定位置移除一项
    removeAt(position) {
        // // 1.越界问题
        if (position < 0 || position > this.length - 1) return null;
        // 2.删除元素
        // 记录第一个节点
        let index = 0;
        let current = this.head; // 当前插入下标的元素
        let previous = null; // 前一个
        // 如果下标为0
        if (position == 0) {
            // 直接将头部等于，当前插入下标的下一个节点
            this.head = current.next
        } else {
            // 如果下标不为0，就一个一个往下找
            while (index++ < position) {
                // 将当前赋值给前一个
                previous = current;
                // 并且当前赋值给当前的下一个
                current = current.next
            }
            // 最后将当前节点的下一个节点赋值给前一个节点的下一个，去掉了当前下标节点
            previous.next = current.next;
        }
        // 最后长度减一
        this.length--
        return current.element
    }
    //  update(position,element)：修改某个位置的元素
    update(position, element) {
        const result = this.removeAt(position);
        this.inset(position, element)
        return result
    }
    //  remove(element)：从列表中移除一项
    remove(element) {
        // 1.获取元素位置
        const index = this.indexOf(element);
        if (index == -1) return -1;
        // 2.删除该位置元素
        this.removeAt(index);
    }
    //  isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false
    isEmpty() {
        return this.length === 0
    }
    //  size()：返回链表包含的元素个数。与数组的length属性类似
    size() {
        return this.length
    }
}